Soit la transformation
\[\Phi(\textbf{x}) = (x^2, \sqrt{2}xy, y^2).\] En appliquant cette transformation sur les données originales, on obtient un problème linéaire.
Mathématiquement, les composantes principales sont obtenues selon une décomposition par valeurs et vecteurs propres de la matrice de covariances
\[ \frac{1}{N} \sum_{i = 1}^{N} \textbf{x}_i\textbf{x}_i^T.\] Correspond à la meilleure projection des données dans une dimension réduite.
On applique une ACP sur les données projetées (Schölkopf, Smola, and Müller 1997). On décompose la matrice de covariances de la matrice des transformations non linéaires
\[ \frac{1}{N} \sum_{i = 1}^{N} \Phi(\textbf{x}_i)\Phi(\textbf{x}_i)^T = \frac{1}{N} \sum_{i = 1}^{N} \textrm{k}(\textrm{x}_i, \textrm{x}_i) .\]
Pour une données à deux attributs \(\textrm{x} = (x_1, x_2)\), on applique la transformation \(\Phi(\textbf{x}) = (x_1^2, \sqrt{2}x_1x_2, x_2^2)\). Le produit scalaire devient
\[ \begin{aligned} (\Phi(\textbf{x}_i) \cdot \Phi(\textbf{x}_j)) &= (x_{i, 1}^2 + \sqrt{2} x_{i, 1} x_{i, 2} + x_{i, 2}^2)(x_{j, 1}^2 + \sqrt{2} x_{j, 1} x_{j, 2} + x_{j, 2}^2)^T\\ &= ((x_{i, 1}x_{i, 2})(x_{j, 1}x_{j, 2})^T)^2\\ &= (\textbf{x}_i \cdot \textbf{x}_j)^2. \end{aligned} \]
On remarque qu’on n’a pas besoin de calculer les valeurs \(x_1^2, \sqrt{2}x_1x_2\) ou \(x_2^2\).
-En général, on projète les données \(\textbf{x}\) dans un espace d’attributs par une transformation non linéaire.
-Formellement, on a
\[ \begin{aligned} \Phi: \mathbb{R}^N &\to \mathcal{F}\\ \textbf{x} &\mapsto \Phi(\textbf{x}) \end{aligned} \]
\[\frac{1}{N} \sum_{i = 1}^{N} \Phi(\textbf{x}_i) \Phi(\textbf{x}_i)^T = \frac{1}{N} \sum_{i = 1}^{N} \textrm{k}(\textrm{x}_i, \textrm{x}_i).\]
Pour le polynome multinomial, on a
\[\Phi(\textrm{x}) = \sum_{\textbf{J} \in \{0, 1, \dots, N\}} w_{\textrm{J}} \prod_{i = 1}^{k}x_{J_i}.\] Ce vecteur contient les données toutes les combinaisons polynomiales de dimension \(k\). Par exemple,
\[x_1^k, x_2^k, \dots, x_p^k,\] \[x_1, x_1^2,\dots, x_1^{k-1}, x_1^{k},\] \[x_1^{k-1}x_2, x_1^{k-2}x_2^2, \dots, x_1 x_2^{k-1},\] \[x_1^{k-1}x_2, x_1^{k-1}x_3, \dots, x_1^{k-1}x_p\]
La transformation produit des données dans une dimension\((p + 1)^k\). Par contre, on peut montrer que
\[\Phi(\textrm{x})\cdot \Phi(\textrm{y}) = (1 + \textrm{x}\cdot \textrm{y})^k = \textrm{k}(\textrm{x}, \textrm{y}).\]
Soit la transformation
\[\Phi_k(\textrm{x}) = \frac{1}{\sqrt{k!}}e^{-\frac{||\textrm{x}||^2}{2}}\prod_{i = 1}^N\frac{x_{J_i}}{\sigma} .\]
On considère l’espace d’attributs de toutes les combinaisons de \(\Phi_k(\textrm{x}), k\in \mathbb{N}\).
Alors, on a
\[\Phi(\textrm{x})\cdot \Phi(\textrm{y}) = e^{-\frac{||\textrm{x} - \textrm{y}||^2}{2\sigma^2}} = \textrm{k}(\textrm{x}, \textrm{y}).\]
La formule \[\frac{1}{N} \sum_{i = 1}^{N} \textrm{k}(\textrm{x}, \textrm{x})\] est valide si les données sont centrées, c-à-d que \[\sum_{i = 1}^{N} \Phi(\textrm{x}_i) = 0.\]
Si \(\Phi(\textrm{x})\) est de dimension infinie, il est impossible de vérifier cette hypothèse.
La solution est proposée par (Schölkopf, Smola, and Müller 1997)
Soit \[K_{ij} = (k(\textbf{x}_i, \textbf{x}_j))_{ij} \textrm{ et } K,\]
la matrice des \(K_{ij}\). Alors, on peut centrer la matrice \(\tilde{K}\) selon
\[\tilde{K}_{ij} = (K - 1_NK - K1_N + 1_NK1_N)_{ij}\]
où \((1_N)_{ij} := \frac{1}{N}\) et éviter de calculer les données \(\Phi(\textbf{x})\).
Rappel : On veut maximiser \(M\) tel que \[y_i(\beta_0 + \beta_1 x_{i1} \dots + \beta_p x_{ip}) \geq M(1 - \varepsilon_i) ~ \forall ~ i = 1, \dots, n\] sous les contraintes \[ \begin{aligned} \sum_{j= 0}^p\beta_j^2 &= 1\\ \varepsilon_i &\geq 0 ~\forall~i\\ \sum_{i = 1}^n\varepsilon_i &\leq c \end{aligned} \]
Avec les multiplicateurs de Lagrange, la fonction à maximiser devient
\[-\frac{1}{2} \sum_{t = 1}^n\sum_{s = 1}^n \alpha_t\alpha_s r_tr_s\textbf{x}_t\textbf{x}_s^T + \sum_{t = 1}^n \alpha_t\] sous les contraintes
\[ \begin{aligned} \sum_{t= 1}^n\alpha_tr_t &= 0\\ 0\leq \alpha_i &\leq c ~\forall~i\\ \end{aligned} \]
On applique l’ACP avec noyau sur le jeu de données MNIST (LeCun et al. 1998).
Kim, Kwang In, Keechul Jung, and Hang Joon Kim. 2002. “Face Recognition Using Kernel Principal Component Analysis.” IEEE Signal Processing Letters 9 (2). IEEE: 40–42.
LeCun, Yann, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. “Gradient-Based Learning Applied to Document Recognition.” Proceedings of the IEEE 86 (11). IEEE: 2278–2324.
Schölkopf, Bernhard, Alexander Smola, and Klaus-Robert Müller. 1997. “Kernel Principal Component Analysis.” In International Conference on Artificial Neural Networks, 583–88. Springer.